"""
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。



示例 1：



输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9


提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
"""


class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        rt = 0

        i = 0
        j = 1
        l = len(height) - 1
        not_found = False
        while i <= l:
            while j <= l:
                i_height = height[i]
                j_height = height[j]
                if j_height < i_height:
                    j += 1
                else:
                    if i + 1 == j and not not_found:
                        i = j
                        j += 1
                        continue

                    if not_found:
                        not_found = False
                        tall = j_height
                    else:
                        tall = i_height

                    for t in range(i, j):
                        rt += tall - height[t]
                        # print(rt)
                    i = j
                    j += 1
                    break
            else:
                not_found = True
                i += 1
                j = i + 1

        return rt


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
height = [4,2,3]
height = [4, 2, 0, 3, 2, 5]
height = [0,7,1,4,6]

print(Solution().trap(height))
